package com.Algorithm.Study.ThinkTest;

import com.TempletGenerate.IntNumGenerate;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2021/10/07/22:34
 * @Description: 每一个数左边比当前数小的数累加起来，叫做这个数组 的小和。求一个数组 的小和。 例子:[1,3,4,2,5] 1左边比1小的数，没有; 3左边比3小的数，1; 4左 边比4小的数，1、3; 2左边比2小的数，1; 5左边比5小的数，1、3、4、 2; 所以小和为1+1+3+1+1+3+4+2=16
 * @Target:小和问题 在一个数组中，
 */
public class MergeSortExtTest {


    public static int smallSum(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }



    public static int process(int arr[], int L, int R){

        while (L==R){
            return 0;
        }
        // 定::要在每一次操作排序时,将右边大于左边的次数统计,并求和
        int M = L + (R-L)>>1;

        return
        process(arr,L,M) +
        process(arr,M+1,R) +
        merge(arr,L,M,R);  // 非叶子节点的都得运行

    }


    public static int merge(int[] arr, int L, int M, int R){
        // ----L----M---    ---M+1----R-----
        int p1=L;
        int p2=M+1;
        int help[] = new int[R-L+1];
        int i = 0;
        int res = 0;


        while (p1<=M&&p2<=R){
            // 135789  246789
            res+=arr[p1]<arr[p2]?(R-p2+1)*arr[p1]:0;   // (R-L+1)记的次数,arr[p1]要记的数
            help[i++]=arr[p1]<arr[p2]?arr[p1++] : arr[p2++];
        }




        while (p1<=M){
            help[i++]=arr[p1++];
        }


        while (p2<=R){
            help[i++]=arr[p2++];
        }


        for (int j = 0; j < help.length; j++) {
            arr[L+j]=help[j];
        }
        return res;


    }


    public static void main(String[] args) {
        IntNumGenerate intNumGenerate = new IntNumGenerate();
        int[] ints = intNumGenerate.RandomInt(10, 1, 10);

        for (int anInt : ints) {
            System.out.print(anInt+ " ");
        }
        System.out.println();

        MergeSortExtTest mergeSortExtTest = new MergeSortExtTest();

        int process = mergeSortExtTest.smallSum(ints);

        System.out.println(process);



    }


}
